package bitonicsequence;

import java.util.Arrays;
public class CandidateCode 
{ 
	public static int bitonic_sequence(int[] a)
	{
		if(a == null || a.length < 1)
			return 0;
		int[] i = new int[a.length];
		for(int p = 1; p < a.length; p++) {
			int m = -1;
			for(int q = 0; q < p; q++)
				if((m < 0 || i[q] > i[m]) && a[q] < a[p])
					m = q;
			if(m >= 0)
				i[p] = i[m] + 1;
		}
		int[] d = new int[a.length];
		for(int p = a.length - 2; p >= 0; p--) {
			int m = -1;
			for(int q = a.length - 1; q > p; q--)
				if((m < 0 || d[q] > d[m]) && a[q] < a[p])
					m = q;
			if(m >= 0)
				d[p] = d[m] + 1;
		}
		int lbs = 0;
		for(int p = 0; p < a.length; p++) {
			int cbs = i[p] + d[p];
			if(cbs > lbs)
				lbs = cbs;
		}
		return lbs + 1;
	}
	public static void main(String[] args) {
		int[][] a = {{1, 11, 2, 10, 4, 5, 2, 1}
		, {12, 11, 40, 5, 3, 1}
		, {80, 60, 30, 40, 20, 10}
		, {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
		, {4, 1, 2, 3, 5}};
		for(int i = 0; i < a.length; i++)
			System.out.println(bitonic_sequence(a[i]) + ": " + Arrays.toString(a[i]));
	}
}
